#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/28 19:48
# @Author  : Yuyun
# @File    : leetcode_516_最长回文子序列.py
# @IDE     : PyCharm
"""
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例 1：
输入：s = "bbbab"
输出：4
解释：一个可能的最长回文子序列为 "bbbb" 。
示例 2：
输入：s = "cbbd"
输出：2
解释：一个可能的最长回文子序列为 "bb" 。
提示：
1 <= s.length <= 1000
s 仅由小写英文字母组成
"""

class Solution:
    """
    dp[i][j]: 从i 到 j的最长回文子序列数
    """
    def max_palindrome(self,s):
        length = len(s)
        dp = [[0]*length for _ in range(length)]
        for i in range(length - 1, -1, -1):
            for j in range(i, length):
                if s[i] == s[j]:
                    if i - j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][-1]

if __name__ == '__main__':
    s = input()
    result_s = Solution().max_palindrome(s)
    print(result_s)